// https://www.lintcode.com/problem/majority-element/description

class Solution {
public:
    /*
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    int majorityNumber(vector<int> &nums) {
        int cnt = 0;
        int major = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (cnt == 0)
            {
                major = nums[i];
            }
            if (nums[i] == major)
            {
                cnt++;
            }
            else
            {
                cnt--;
            }
        }
        return major;
    }
};